package leetcode_1100;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 *@author 周杨
 *MaximizeSumOfArrayAfterKNegations_1005 一个数组 可以被翻转k次 一个元素可以被反复翻转 问最终最大数组和是多少
 *describe:用堆记录负数 一个常量记录正数的最小值 
 *2019年3月19日 下午23:05
 */
public class MaximizeSumOfArrayAfterKNegations_1005 {
	public int largestSumAfterKNegations(int[] A, int K) {
		Queue<Integer> neg = new PriorityQueue<Integer>();
		int pos = Integer.MAX_VALUE;
		int sum = 0;
		for (int i : A) {
			if (i >= 0)
				pos = Math.min(pos, i);// 只保留正数的最小数
			if (i < 0)
				neg.offer(i);
			sum += i;
		}
		if (neg.size() == 0) {
			if (K % 2 == 1)
				sum -= 2 * pos;
			return sum;
		}
		while (K > 0 && neg.size() > 1) {
			int now = neg.poll();
			sum += -2 * now;
			pos = Math.min(pos, -now);
			--K;
		}
		if (K == 0)
			return sum;
		if (K % 2 == 1)
			sum += -2 * neg.poll();
		else {
			int last = neg.poll();
			if (-last > pos)
				sum += 2 * (-last - pos);
		}
		return sum;
	}
}
